Search for: All records

Reconfigurable datacenter networks use fast optical circuit switches to provide high bandwidths at low cost, therefore emerging as a compelling alternative to packet switching. These switches offer micro- and nano-second reconfiguration, and reacting to demand at this time scale is infeasible. Proposed designs have therefore largely been oblivious, supporting arbitrary traffic patterns. However, this imposes a fundamental latency-throughput tradeoff that significantly limits the benefits of these switches. In this paper, we illustrate the feasibility of semi-oblivious reconfigurable datacenter networks that periodically adapt to large-scale structural patterns in traffic. We argue that such patterns are predictable in modern datacenters, that optimizing for them can provide latency-throughput scaling superior to oblivious designs, and that existing fast circuit-switched technologies support coarse-grained flexibility to adapt to these patterns. 

Circuit-switched technologies have long been proposed for handling high-throughput traffic in datacenter networks, but recent developments in nanosecond-scale reconfiguration have created the enticing possibility of handling low-latency traffic as well. The novel Oblivious Reconfigurable Network (ORN) design paradigm promises to deliver on this possibility. Prior work in ORN designs achieved latencies that scale linearly with system size, making them unsuitable for large-scale deployments. Recent theoretical work showed that ORNs can achieve far better latency scaling, proposing theoretical ORN designs that are Pareto optimal in latency and throughput. In this work, we bridge multiple gaps between theory and practice to develop Shale, the first ORN capable of providing low-latency networking at datacenter scale while still guaranteeing high throughput. By interleaving multiple Pareto optimal schedules in parallel, both latency- and throughput-sensitive flows can achieve optimal performance. To achieve the theoretical low latencies in practice, we design a new congestion control mechanism which is best suited to the characteristics of Shale. In datacenter-scale packet simulations, our design compares favorably with both an in-network congestion mitigation strategy, modern receiver-driven protocols such as NDP, and an idealized analog for sender-driven protocols. We implement an FPGA-based prototype of Shale, achieving orders of magnitude better resource scaling than existing ORN proposals. Finally, we extend our congestion control solution to handle node and link failures. 

In a landmark 1981 paper, Valiant and Brebner gave birth to the study of oblivious routing and, simultaneously, introduced its most powerful and ubiquitous method: Valiant load balancing (VLB). By routing messages through a randomly sampled intermediate node, VLB lengthens routing paths by a factor of two but gains the crucial property of obliviousness: it balances load in a completely decentralized manner, with no global knowledge of the communication pattern. Forty years later, with datacenters handling workloads whose communication pattern varies too rapidly to allow centralized coordination, oblivious routing is as relevant as ever, and VLB continues to take center stage as a widely used — and in some settings, provably optimal — way to balance load in the network obliviously to the traffic demands. However, the ability of the network to rapidly reconfigure its interconnection topology gives rise to new possibilities. In this work we revisit the question of whether VLB remains optimal in the novel setting of reconfigurable networks. Prior work showed that VLB achieves the optimal tradeoff between latency and guaranteed throughput. In this work we show that a strictly superior latency-throughput tradeoff is achievable when the throughput bound is relaxed to hold with high probability. The same improved tradeoff is also achievable with guaranteed throughput under time-stationary demands, provided the latency bound is relaxed to hold with high probability and that the network is allowed to be semi-oblivious, using an oblivious (randomized) connection schedule but demand-aware routing. We prove that the latter result is not achievable by any fully-oblivious reconfigurable network design, marking a rare case in which semi-oblivious routing has a provable asymptotic advantage over oblivious routing. Our results are enabled by a novel oblivious routing scheme that improves VLB by stretching routing paths the minimum possible amount — an additive stretch of 1 rather than a multiplicative stretch of 2 — yet still manages to balance load with high probability when either the traffic demand matrix or the network’s interconnection schedule are shuffled by a uniformly random permutation. To analyze our routing scheme we prove an exponential tail bound which may be of independent interest, concerning the distribution of values of a bilinear form on an orbit of a permutation group action. 

Abstract Social relationships among animals emerge from interactions in multiple ecological and social situations. However, we seldom ask how each situation contributes to the global structure of a population, and whether different situations contribute different information about social relationships and the position of individuals within the social fabric. Griffon vultures (Gyps fulvus) interact socially in multiple situations, including communal roosting, joint flights, and co‐feeding. These social interactions can influence population‐level outcomes, such as disease transmission and information sharing that determine survival and response to changes. We examined the unique contribution of each social and ecological situation to the social structure of the population and individuals' positions within the overall social network using high‐resolution GPS tracking. We found that the number of individuals each vulture interacted with (degree) was best predicted by diurnal interactions—both during flights and on the ground (such as when feeding). However, the strength of social bonds, that is, the number of interactions an individual had (strength), was best predicted by interactions on the ground—both during the day (e.g., while feeding) and at night (e.g., while roosting) but not by interactions while flying. Thus, social situations differ in their impact on the relationships that individuals form. By incorporating the ecological situations in which social interactions occur we gain a more complete view of how social relationships are formed and which situations are important for different types of interactions. 

Abstract We report on a full-polarization analysis of the first 25 as yet nonrepeating fast radio bursts (FRBs) detected at 1.4 GHz by the 110-antenna Deep Synoptic Array (DSA-110) during commissioning observations. We present details of the data-reduction, calibration, and analysis procedures developed for this novel instrument. Faraday rotation measures (RMs) are searched between ±10⁶rad m⁻²and detected for 20 FRBs, with magnitudes ranging from 4 to 4670 rad m⁻². Fifteen out of 25 FRBs are consistent with 100% polarization, 10 of which have high (≥70%) linear-polarization fractions and two of which have high (≥30%) circular-polarization fractions. Our results disfavor multipath RM scattering as a dominant depolarization mechanism. Polarization-state and possible RM variations are observed in the four FRBs with multiple subcomponents. We combine the DSA-110 sample with polarimetry of previously published FRBs, and compare the polarization properties of FRB subpopulations and FRBs with Galactic pulsars. Although FRB polarization fractions are typically higher than those of Galactic pulsars, and cover a wider range than those of pulsar single pulses, they resemble those of the youngest (characteristic ages <10⁵yr) pulsars. Our results support a scenario wherein FRB emission is intrinsically highly linearly polarized, and propagation effects can result in conversion to circular polarization and depolarization. Young pulsar emission and magnetospheric propagation geometries may form a useful analogy for the origin of FRB polarization. 

Abstract The stellar population environments that are associated with fast radio burst (FRB) sources provide important insights for developing their progenitor theories. We expand the diversity of known FRB host environments by reporting two FRBs in massive galaxy clusters that were discovered by the Deep Synoptic Array (DSA-110) during its commissioning observations. FRB 20220914A has been localized to a star-forming, late-type galaxy at a redshift of 0.1139 with multiple starbursts at lookback times less than ∼3.5 Gyr in the A2310 galaxy cluster. Although the host galaxy of FRB 20220914A is similar to typical FRB hosts, the FRB 20220509G host stands out as a quiescent, early-type galaxy at a redshift of 0.0894 in the A2311 galaxy cluster. The discovery of FRBs in both late- and early-type galaxies adds to the body of evidence that the FRB sources have multiple formation channels. Therefore, even though FRB hosts are typically star-forming, there must exist formation channels that are consistent with old stellar population in galaxies. The varied star formation histories of the two FRB hosts that we report here indicate a wide delay-time distribution of FRB progenitors. Future work in constraining the FRB delay-time distribution, using the methods that we develop herein, will prove crucial in determining the evolutionary histories of FRB sources. 

Abstract The hot gas that constitutes the intracluster medium (ICM) has been studied at X-ray and millimeter/submillimeter wavelengths (Sunyaev–Zel’dovich effect) for decades. Fast radio bursts (FRBs) offer an additional method of directly measuring the ICM and gas surrounding clusters via observables such as dispersion measure (DM) and Faraday rotation measure. We report the discovery of two FRB sources detected with the Deep Synoptic Array whose host galaxies belong to massive galaxy clusters. In both cases, the FRBs exhibit excess extragalactic DM, some of which likely originate in the ICM of their respective clusters. FRB 20220914A resides in the galaxy cluster A2310 at z = 0.1125 with a projected offset from the cluster center of 520 ± 50 kpc. The host of a second source, FRB 20220509G, is an elliptical galaxy at z = 0.0894 that belongs to the galaxy cluster A2311 at the projected offset of 870 ± 50 kpc. These sources represent the first time an FRB has been localized to a galaxy cluster. We combine our FRB data with archival X-ray, Sunyaev–Zel'dovich (SZ), and optical observations of these clusters in order to infer properties of the ICM, including a measurement of gas temperature from DM and y SZ of 0.8–3.9 keV. We then compare our results to massive cluster halos from the IllustrisTNG simulation. Finally, we describe how large samples of localized FRBs from future surveys will constrain the ICM, particularly beyond the virial radius of clusters.